package leetcode_100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *MinimumWindowSubstring_76 同样是建立一个字典，然后维护一个窗口。区别是在这道题目中，因为可以跳过没在字典里面的字符（也就是这个串不需要包含且仅仅包含字典里面的字符，有一些不在字典的仍然可以满足要求），所以遇到没在字典里面的字符可以继续移动窗口右端，而移动窗口左端的条件是当找到满足条件的串之后，一直移动窗口左端直到有字典里的字符不再在窗口里。在实现中就是维护一个HashMap，一开始key包含字典中所有字符，value就是该字符的数量，然后遇到字典中字符时就将对应字符的数量减一。算法的时间复杂度是O(n),其中n是字符串的长度，
 *因为每个字符再维护窗口的过程中不会被访问多于两次。
 *空间复杂度则是O(字典的大小)，也就是代码中T的长度
 *describe: AC 40%
 *2018年5月13日 下午8:45:40
 */
public class MinimumWindowSubstring_76 {

	public static void main(String[] args) {
		MinimumWindowSubstring_76 test=new MinimumWindowSubstring_76();
		/*System.out.println(test.minWindow("ADOBECODEBANC", "ABC"));
		System.out.println(test.minWindow("cabefgecdaecf", "cae"));
		System.out.println(test.minWindow("ab", "b"));
		System.out.println(test.minWindow("b", "b"));*/
		System.out.println(test.minWindow_("bba", "ab"));

	}
	
	public String minWindow_(String s, String t) {
		if(s==null || s.length()==0) return "";
		Map<Character,Integer> map=new HashMap<Character,Integer>();
		char []charst=t.toCharArray();
		for(char c:charst) {
			map.put(c, map.getOrDefault(c, 0)+1);
		}
		char []chars=s.toCharArray();
		int count=0,left=0,min=s.length()+1,start=0;
		for(int right=0;right<s.length();++right) {
			char now=chars[right];
			if(map.containsKey(now)) {
				map.put(now, map.get(now)-1);
				if(map.get(now)>=0) {
					++count;
					while(count==t.length()) {
						if(right-left+1<min) {
							min=right-left+1;
							start=left;
						}
						if(map.containsKey(chars[left])) {
							map.put(chars[left], map.get(chars[left])+1);
							if(map.get(chars[left])>0)
								--count;
							
						}
						++left;
					}
				}
			}
		}
		return min>s.length()?"":s.substring(start,start+min);
	}
	
	
	public String minWindow1(String s, String t) {
		if(s==null || s.length()==0)  
	        return "";  
	    HashMap<Character, Integer> map = new HashMap<Character, Integer>();  
	    for(int i=0; i<t.length();i++)  
	    {  
	        if(map.containsKey(t.charAt(i)))  
	        {  
	            map.put(t.charAt(i),map.get(t.charAt(i))+1);  
	        }  
	        else  
	        {  
	            map.put(t.charAt(i),1);  
	        }  
	    }  
	    int left = 0;  
	    int count = 0;  
	    int minLen = s.length()+1;  
	    int minStart = 0;  
	    for(int right=0; right<s.length();right++)  
	    {  
	        if(map.containsKey(s.charAt(right)))  
	        {  
	            map.put(s.charAt(right),map.get(s.charAt(right))-1);  
	            if(map.get(s.charAt(right))>=0)  
	            {  
	                count++;  
	            }  
	            while(count == t.length())  
	            {  
	                if(right-left+1<minLen)  
	                {  
	                    minLen = right-left+1;  
	                    minStart = left;                      
	                }  
	                if(map.containsKey(s.charAt(left)))  
	                {  
	                    map.put(s.charAt(left), map.get(s.charAt(left))+1);  
	                    if(map.get(s.charAt(left))>0)  
	                    {  
	                        count--;  
	                    }  
	                }  
	                left++;  
	            }  
	        }  
	    }  
	    if(minLen>s.length())  
	    {  
	        return "";  
	    }  
	    return s.substring(minStart,minStart+minLen);  
	}
	
    public String minWindow(String s, String t) {
        int asc[]=new int[256];//存入ASC码数组 记录每个字符出现几次
        boolean help[]=new boolean[256];
        for(int i=0;i<t.length();++i) {
        	asc[t.charAt(i)]++;
        	help[t.charAt(i)]=true;
        }
        List<Integer> index=new ArrayList<Integer>();
        List<Integer> charSer=new ArrayList<Integer>();
        int start=0,end=0,run=0,min=Integer.MAX_VALUE,total=t.length(),minEnd=0,minStart=0;
        boolean flag=false;
        while(run<s.length()) {
        	char c=s.charAt(run);
        	if(help[c]) {//此字符被收录
        		if(flag) {//此时已经有最小窗口了 开始更新窗口
        			
        			for(int i=0;i<index.size();++i) {
        				int nowChar=charSer.get(i);
        				 //移除其他
        				total++;
        				flag=false;
        				++asc[nowChar];
        				index.remove(i);
        				charSer.remove(i);
        				--i;
        				if(nowChar==(int)c) {//是此处
        					break;
        				}
        			
        			}
        			--total;
        			asc[c]--;
        			index.add(run);
    				charSer.add((int)c);
        			start=index.get(0);
    				if(total==0) {//此时建立窗口
    					end=run+1;
    					if(end-start<min) {
    						minEnd=end;
    						minStart=start;
    						min=end-start;
    					}
    					flag=true;
    				}
        		}
        		else {
        			if(asc[c]>0) {//仍然有个数可以匹配
        				if(total==t.length())
        					start=run;
        				index.add(run);
        				charSer.add((int)c);
        				asc[c]--;
        				total--;
        				if(total==0) {//此时建立窗口
        					end=run+1;
        					if(end-start<min) {
        						minEnd=end;
        						minStart=start;
        						min=end-start;
        					}
        					flag=true;
        				}
        			}
        		}
        	}
        	++run;
        }
        if(minEnd==0)
        	return "";
        return s.substring(minStart, end);
    }

}
